class Solution
{
public:
    int stoneGameII(vector<int> &piles)
    {
        int n = piles.size();
        vector<vector<int>> f(n + 2, vector<int>(n + 1));
        vector<int> s(n + 1);
        for (int i = 1; i <= n; i ++ )
            s[i] = s[i - 1] + piles[i - 1];//pile下标从0开始的

        for (int i = n; i; i -- )//从后往前更新i
        {
            for (int j = 1; j <= n; j ++ )//枚举不同的x
            {
                for (int k = 1; i + k - 1 <= n && k <= j * 2; k ++ )//枚举不同的m
                {
                    f[i][j] = max(f[i][j], s[n] - s[i - 1] - f[i + k][max(k, j)]);
                }
            }
        }

        return f[1][1];
    }
};



//f[i][j]表示当前剩余的石子是i-> n,当前m=j的时候,我们先手能取到的分值最大是多少

//转移O(n) f(i,j)= sn-s(i-1)-min{f(i+k,max(k,m)}  //这个min求的是对手的
//状态O(n^2)

//初值是f(n+1,j)=0

